Tổ tiên của ông là một trong các bộ tộc thuộc Bắc Ngụy, cư trú ở sông Khố Hộc Chân [2]. Tổ 5 đời gọi là Thái Cốt Đô hầu. Con cháu đời đời làm Cừ soái. Ông là Hầu Mạc Trần Doãn hưởng ứng việc dời con em quý tộc đến Lục trấn, đưa cả nhà đến trấn Vũ Xuyên. Cha là Hầu Mạc Trần Hưng, làm Điện trung tướng quân, Vũ Lâm giám.

Sùng từ nhỏ kiêu dũng, giỏi bắn cung, cẩn thận ít lời. Lên 15 tuổi, theo Hạ Bạt Nhạc cùng Nhĩ Chu Vinh đi đánh Cát Vinh. Lại theo Nguyên Thiên Mục dẹp Hình Cảo. Bình xong, nhờ công được làm Kiến uy tướng quân. Theo Nhạc phá Nguyên Hạo ở Lạc Dương. Được thăng làm Trực tẩm.

Sau đó Nhạc vào Quan, phá người Thục ở Xích Thủy. Khi ấy Mặc Kỳ Sửu Nô vây Kỳ Châu, sai bộ tướng Uất Trì Bồ Tát đem quân hướng đến Võ Công. Sùng theo Nhạc ra sức chiến đấu, phá được, thừa thắng đuổi lên phía bắc, giải vây Kỳ Châu. Lại đến sông Bách Lý Tế Xuyên [3], phá công sự của Hầu Phục Hầu Nguyên Tiến. Sửu Nô đưa tàn quân chạy đi Cao Bình, Sùng cùng khinh kị đuổi theo, đến Trường Khanh, Kính Châu thì kịp. Nghĩa quân chưa bày trận xong, ông một ngựa xông vào, bắt sống Sửu Nô trên lưng ngựa. Sùng hô lớn, nghĩa quân dạt tránh, không dám chống lại. Sau đó kỵ binh Bắc Ngụy đến đánh, nghĩa quân tan chạy bỏ trốn, nên đại bại. Nhạc lấy ngựa cùng bảo kiếm, đai vàng của Sửu Nô thưởng Sùng. Được làm An bắc tướng quân, Thái trung đại phu, đô đốc, phong Lâm Kính huyện hầu, thực ấp 800 hộ.

Khi Nhạc bị Hầu Mạc Trần Duyệt hại, Sùng cùng các tướng đón Vũ Văn Thái. Thái sai ông tập kích bộ hạ của Duyệt là Nguyên Châu thứ sử Sử Quy. Sùng trong đêm tiến quân, đưa 7 kỵ binh thẳng đến dưới thành, còn lại đều ở bên đường. Quy thấy ít quân, nên không đề phòng. Sùng lập tức vào chiếm cửa thành. Khi ấy anh em Lý Viễn ở trong thành khởi binh, trong ngoài nổi trống, bắt Quy, chém đầu. Thái lấy Sùng làm Hành Nguyên Châu sự. Tiếp tục theo quân bình Duyệt, được thăng làm Chinh tây tướng quân. Lại sai Sùng phủ dụ Tần Châu, riêng phong Quảng Vũ huyện bá, thực ấp 700 hộ.